package xio.leetcode.java;

import xio.leetcode.java.base.ListNode;

import java.util.ArrayList;

/**
 * leetcode 23
 * Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
 *
 * 归并k个已排序链表，可以分解问题拆解成为，重复k次，归并2个已排序链表，即：
 *         ListNode l1 = lists.get(0);
 *         for (int i = 1; i < lists.size(); i++) {
 *             l1 = mergeTwoLists(l1,lists.get(i));
 *         }
 *         return l1;
 *  但这样总共需要 k 次merge two sorted lists的合并过程，时间复杂度是O(kn),会超出 oj 的时间限制；
 *
 *  采用分治法，将包含k个链表的列表逐次分成两个部分，再逐次对两个链表合并，这样就有 log(k)次合并过程，
 *  每次均使用merge two sorted lists的算法。时间复杂度O(nlog(k)
 *
 *
 * 分治解法
 * 时间复杂度：O(nlogk) 空间复杂度: O(logk)
 */
public class LC23_MergeKSortedLists {
    public ListNode mergeKLists(ArrayList<ListNode> lists) {
        if(lists.size() == 0){
            return null;
        }
        return sort(lists,0,lists.size()-1);

    }

    /**
     * 分治法
     * @param lists k个链表的集合
     * @param lo 第lo个链表
     * @param hi 第hi个链表
     * @return 排序好的链表
     */
    private ListNode sort(ArrayList<ListNode> lists, int lo, int hi){
        if (lo >= hi){
            return lists.get(lo);
        }
        int mid = (hi - lo)/2 + lo;
        ListNode l1 = sort(lists,lo,mid);
        ListNode l2 = sort(lists, mid+1,hi);
        return mergeTwoLists(l1,l2);
    }

    /**
     * 合并两个sorted 链表
     * @param l1 链表l1
     * @param l2 链表l2
     * @return 合并后的链表
     */
    private ListNode mergeTwoLists(ListNode l1, ListNode l2) {

        if (l1 != null && l2 != null){
            if (l1.val > l2.val){
                l2.next = mergeTwoLists(l1,l2.next);
                return l2;
            }else {
                l1.next = mergeTwoLists(l1.next,l2);
                return l1;
            }
        }else {
            return l1 == null? l2:l1;
        }
    }
}
